﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CodeCheef.Tasks
{
    /*
     All submissions for this problem are available.

According to many researches, people can stand on a bus for several hours, but waiting for a bus for more than 30 minutes at a bus station can make us exhausted. The Chef is a perfect example for this fact. He always tries to reduce the longest period of time of waiting for a bus. Therefore, optimizing the traveling plan for him is far from an easy task.
Let's consider the bus system with N bus stations (numbered from 1 to N) and M buses (numbered from 1 to M). Each bus is represented by 4 integer numbers U, V, S, E which means it will start at the bus station U at the time S and arrive at the bus station V at the time E with no intermediate bus stations. If passenger arrives at the bus station U at the time X ≤ S, he has to wait for S − X units of time to catch this bus. Note, that if he arrives at the bus station U exactly at time S he can catch this bus with no waiting time.
The Chef starts at the time 0 in the bus station 1, and he wants to arrive at the bus station N in a way that the longest period that he spends for waiting for a bus is as small as possible. Besides, he must be at the bus station N before or at the time T for a specially important meeting. Note, that he may wait for a meeting if he arrives at the bus station N early but that period is not our concern here, since he doesn't wait for any bus at that time.
Input

The first line of the input contains three space-separated integers N, T and M, denoting the number of bus stations, the deadline for coming to bus station N and the number of buses, respectively. Each of the following M lines contains four space-separated integers U, V, S, E, the parameters of the current bus as described in the problem statement.
Output

If Chef cannot arrive at the bus station N before or at the time T, output -1. Otherwise, output the maximum period of time he has to wait for a bus in the optimal traveling plan.
Constraints

 
2 ≤ N ≤ 50000
1 ≤ T ≤ 109
1 ≤ M ≤ 100000 (105)
1 ≤ U ≤ N
1 ≤ V ≤ N
U ≠ V
0 ≤ S < E ≤ 109
 
Example

Input:
5 10 5
1 2 1 2
1 5 3 4
2 4 4 5
2 5 5 6
4 5 6 7

Output:
2
Explanation

There are three different traveling plans:
bus 1 → bus 3 → bus 5. His waiting time for each bus is 1, 2, 1, respectively.
bus 2. His waiting time is 3.
bus 1 → bus 4. His waiting time for each bus is 1, 3, respectively.
 
For each traveling plan Chef arrives at the bus station N = 5 before the time T = 10. But only the first traveling plan is optimal, since the longest period of time his has to wait is 2.
     */
    public class TravelingPlan:AbstractTask
    {
        public void PrepareData()
        {
            throw new NotImplementedException();
        }

        public void Run()
        {
            throw new NotImplementedException();
        }
    }
}
